import heapq


class Solution(object):
    def kthSmallest(self, mat, k):
        m = len(mat)
        n = len(mat[0])
        val = sum(mat[i][0] for i in range(m))
        st = [[val, tuple([0] * m)]]
        index = 0
        already = {tuple([0] * m)}
        while index < k:
            val, index_list = heapq.heappop(st)
            for i in range(m):
                if index_list[i] < n - 1:
                    next_index = list(index_list)
                    next_index[i] += 1
                    next_val = val + mat[i][next_index[i]] - mat[i][index_list[i]]
                    tuple_next_index = tuple(next_index)
                    if tuple_next_index not in already:
                        already.add(tuple_next_index)
                        heapq.heappush(st, [next_val, tuple_next_index])
            index += 1
        return val


data = Solution()
mat = [[1, 3, 11], [2, 4, 6]]
k = 9
print(data.kthSmallest(mat, k))
